The importance of a fast, low-cost adder in a digital system is difficult to overestimate. Not only are adders used in every arithmetic operation, they are also needed for computing the physical address in virtually every memory fetch operation in most modern CPUs. Adders are also used in many other digital systems including telecommunications systems in places where a full-fledged CPU would be superfluous. Many styles of adders exist. Ripple adders are the smallest but also the slowest. More recently, carry-skip adders, as described in Koren, I.: “Computer Arithmetic Algorithms,” Prentice-Hall, 1993; Kantabutra, V.: “Designing Optimum One-Level Carry-Skip Adders,” IEEE Trans. on Comp., 1993, Vol. 42, n.6, pp. 759–764; and Chan, P. K., Schlag, M. D. F., Thomborson, C. D. Oklobdzija, V. G.: “Delay Optimization of Carry-Skip Adders and Block Carry-Look-Ahead Adders,” Proc. of Int'l Symposium on Computer Arithmetic, 1991, pp. 154–164, are gaining popularity due to their high speed and relatively small size. Normally, in an N-bit carry-skip adder divided into a proper number of M-bit blocks, as described in Koren, I.: “Computer Arithmetic Algorithms,” Prentice-Hall, 1993; Nagendra, C., Irwin, M. J., Owens, R. M.: “Area-Time-Power Tradeoffs in Parallel Adders,” IEEE Trans. CAS-II, 43, (10), pp. 689–702, a long-range carry signal starts at a generic block Bi, rippling through some bits in that block, then skips some blocks, and ends in a block Bj. If the carry does not end at the LSB of Bj, then rippling occurs in that block and an additional delay is needed to compute the valid sum bits. Carry-look-ahead and carry-select adders as described in Koren, I.: “Computer Arithmetic Algorithms,” Prentice-Hall, 1993 are fast but larger and consume much more power than ripple or carry-skip adders.
Two of the fastest known addition circuits are the Lynch-Swartzlander type as described in T. Lynch, E. E. Swartzlander, “A spanning-tree carry-look-ahead adder,” IEEE Trans. on Comp., Vol. 41, n.8, August 1992 and the Kantabutra type as described in Kantabutra, “A Recursive Carry-Look-Ahead/Carry-Select Hybrid Adder,” IEEE Trans. on Comp., Vol. 42, n.12, December 1993. These hybrid carry-look-ahead type adders are also described in U.S. Pat. No. 5,508,952, filed Oct. 19, 1993 which is entitled “Carry-LookAhead/Carry-Select Binary Adder,” which is incorporated herein by reference in its entirety. They are based on the usage of a carry tree that produces carries into appropriate bit positions without back propagation. In order to obtain the valid sum bits as soon as possible, in both Lynch-Swartzlander type and Kantabutra type adders the sum bits are computed by means of carry-select blocks, which are able to perform their operations in parallel with the carry-tree.
A further known adder design is called the Carry-Increment Adder (CIA) as described in R. Zimmermann and H. Kaeslin, “Cell-Based Multilevel Carry-Increment Adders with Minimal AT-and PT-Products, unpublished manuscript at http://www.iis.ee.ethz.ch/˜zimmi/extending the work in A. Tyagi, “A Reduced-Area Scheme for Carry-Select Adders,” IEEE Trans. on Comp., Vol. 42, n.10, October 1993. These articles discuss reducing the redundancy in carry-select adders, and propose adders that are described as minimally slower than regular carry-select adders, requiring significantly less space.